This invention relates to devices and methods for bus arbitration of a common bus shared by a plurality of users. More specifically, the invention relates to a bus arbitration apparatus and method which uses a least recently used (LRU) algorithm while having a programmable priority mode feature for providing bus users of a high priority greater access to the bus over low priority bus users, and provisions for monitoring bus activity.
In computer systems, design tradeoffs in circuit packaging, technology, cost and system performance often result in the implementation of shared buses for the transfer of information such as data, commands or other messages. In systems that utilize high speed parallel buses which interconnect several devices of similar function and bus priority, it is necessary that each device be given sufficient allocation in bus access to balance bus utilization, i.e., bandwidth. For optimum operation, it is also necessary that the average wait time for all devices in accessing the bus be as small as possible. It is further necessary for optimum performance that the arbitration mechanism which determines priority in access to the shared bus to be as fast as possible, particularly in terms of logic level transitions, to calculate the next device grant.
In bus arbitration schemes, several algorithms have been previously utilized in various forms. The most widely used algorithms for bus arbitration schemes use fixed priority. The most widely used dynamic algorithms are: the least recently used (LRU); the rotating daisy chain; and the first come, first serve. Implementation of a "dynamic" algorithm, such as the LRU algorithm in bus arbitration mechanisms is more desirable than other algorithm types, since the "dynamic" algorithm is typically more efficient in determining allocation of shared bus resources. However, the "dynamic" algorithms such as the LRU algorithm, are more expensive in logic element count and logic delays to implement. Regardless of the algorithm chosen, it is desirable to provide a high-speed implementation utilizing minimal delays in minimal logic circuitry. In the CMOS technology, particularly in the large scale integration technology, the speed of the arbiter is particularly important since off-chip driver delays are typically slow.
In selecting a bus arbitration algorithm, an important factor of consideration is the diversity of the input/output (I/O) devices attached to the system. Data processing systems typically have both time critical devices, such as direct access storage devices (DASD), along with less bandwidth intensive communications devices, such as printers. It is, therefore, desirable to give time-critical devices a higher percentage of bus bandwidth than slower devices.
The LRU algorithm has been incorporated into several dynamic bus arbitration mechanisms. One such implementation of an LRU algorithm is disclosed in U.S. Pat. No. 4,672,536, assigned to the Assignee of the present invention. In this implementation, an age value is assigned to each bus unit attached to a shared common bus. The requesting bus unit is granted access to the bus if it has an age value corresponding to the oldest request. However, implementation of this LRU arbitration scheme is slow; and requires substantial amounts of circuitry and input/output signals.
Another example of an LRU algorithm embodied in a bus arbitration scheme is disclosed in U.S. Pat. No. 4,663,756. In this particular bus arbiter, a memory is utilized to store priority codes assigned to bus units. These priority codes are used by the bus arbiter to determine which bus unit will have the highest priority after a grant. After a bus unit with the highest priority code has accessed the bus, its priority code is then set to the lowest priority with the priority of all other channels incremented by one. However, due to combinatorial logic limitations the disclosed bus arbiter will not always grant access to the bus in accordance with a pure LRU algorithm. Furthermore, utilization of a memory device also requires a substantial amount of associated circuitry and costs.
In certain applications of a bus arbitration scheme, it is desirable that certain bus units be given higher priority in access to the shared bus. It is desirable in these applications that the LRU algorithm be utilized in arbitration of bus requests between bus units in the high priority class. Furthermore, it is desirable that the LRU algorithm be utilized in arbitration of bus requests between bus units in the low priority class. According to this arbitration scheme, all high priority class bus requests would be serviced prior to servicing of low priority class bus requests.
In order to achieve optimum bus performance, it is necessary to balance bus utilization. Therefore, bus activity must be monitored to determine the activity relative to each bus user. Monitoring of bus activity is typically accomplished by including in the hardware, physical monitoring points to which monitoring devices are connected. Once a determination is made with respect to bus user activity, devices on one bus unit may be interchanged with devices on another bus unit. Thus, a bus unit with a high level of bus activity, as a result of having several high activity devices, can have one or more of the high activity devices exchanged with low activity devices of another bus unit. With the advent of very large-scale integration (VLSI) chip technology, it is difficult to monitor real time demand on shared buses by connecting measurement devices to hardware monitor points.